typedef struct BiTNode // 结点结构
{
	ElemType data;
	struct BiTNode  *lchild, *rchild; 	// 左右孩子指针
} BiTNode, *BiTree;
BiTree T  // 二叉链表的根指针

Status SearchBST (BiTree T, ElemType key, BiTree f, BiTree p )
{
  /* 
     在根指针 T 所指二叉排序树中递归地查找其
     关键字等于 key 的数据元素，若查找成功，
     则返回指针 p 指向该数据元素的结点，并返回
     函数值为 TRUE; 否则表明查找不成功，返回
     指针 p 指向查找路径上访问的最后一个结点，
     并返回函数值为FALSE, 指针 f 指向当前访问
     的结点的双亲，其初始调用值为NULL
  */
	if (!T)
	{
		p = f;
		return FALSE;
	}  // 查找不成功
	else  if ( key == T->data )
	{
		p = T;
		return TRUE;
	}  // 查找成功
	else if ( key < T->data )	// 在左子树中继续查找
		SearchBST (T->lchild, key, T, p );                      
	else 	// 在右子树中继续查找
		SearchBST (T->rchild, key, T, p );
} // SearchBST

Status Insert BST(BiTree T, ElemType e ) 
{ 
  // 二叉搜索树中若不存在关键字等于 e 的数据
  // 元素，则插入值为 e 的结点，并返回 TRUE; 
  // 否则，不进行插入并返回FALSE
	if (!SearchBST ( T, e, NULL, p ))
	{                             
		s = (BiTNode*)malloc(sizeof(BiTNode)); // 为新结点分配空间
		s->data = e;  
		s->lchild = s->rchild = NULL;  
		if(!p)
			T = s;     // 插入 s 为新的根结点
		else if ( e < p->data ) 
			p->lchild = s;    // 插入 *s 为 *p 的左孩子
		else  
			p->rchild = s;  // 插入 *s 为 *p 的右孩子
		return TRUE;       // 插入成功
	}
	else return FALSE;
} // Insert BST

Status DeleteBST (BiTree T,  ElemType key ) 
{
  // 若二叉搜索树 T 中存在其关键字等于 key 的
  // 数据元素，则删除该数据元素结点，并返回
  // 函数值 TRUE，否则返回函数值 FALSE
	if (!T)  return FALSE;  // 不存在关键字key
	else
	{
		if ( key == T->data ) // 找到关键字等于key的数据元素
		{
			Delete (T);
			return TRUE;
		}
		else if ( key < T->data ) // 继续在左子树中进行查找
			DeleteBST ( T->lchild, key );	
		else
			DeleteBST ( T->rchild, key ); // 继续在右子树中进行查找
	}
} // DeleteBST

void Delete ( BiTree p )
{
	// 从二叉排序树中删除结点 p，并重接左右子树
	if (!p->rchild)  
	{
		q = p;
		p = p->lchild;
		free(q);
	} 
	else if (!p->lchild) 
	{
		q = p;
		p = p->rchild;
		free(q);
	} 
	else
	{
		q = p;
		s = p->lchild;
		while (s->rchild)
		{ 
			q = s;
			s = s->rchild; // s 指向被删结点的前驱
		}
		p->data = s->data;
		if (q != p )  
			q->rchild = s->lchild;             
		else
			q->lchild = s->lchild;	// 重接*q的左子树
		free(s);
	}
} // Delete

void Preorder (BiTree T) // 先序遍历二叉树 
{ 
	if (T) 
	{
		printf(T->data);	// 访问结点
		Postorder(T->lchild);   // 遍历左子树
		Postorder(T->rchild);  // 遍历右子树
	}
}

void Inorder (BiTree T) // 中序遍历二叉树 
{ 
	if (T) 
	{
		Postorder(T->lchild);   // 遍历左子树
		printf(T->data);	// 访问结点
		Postorder(T->rchild);  // 遍历右子树
	}
}

void Postorder (BiTree T) // 后序遍历二叉树 
{ 
	if (T) 
	{
		Postorder(T->lchild);   // 遍历左子树
		Postorder(T->rchild);  // 遍历右子树
		printf(T->data);	// 访问结点
	}
}